public class Tree {
    public static class Node {
        public char val;
        public Node left;
        public Node right;

        public Node(char val) {
            this.val = val;
        }
    }

    //跟节点
    public Node creatTree() {
        Node A = new Node('A');
        Node B = new Node('B');
        Node C = new Node('C');
        Node D = new Node('D');
        Node E = new Node('E');
        Node F = new Node('F');
        Node G = new Node('G');
        Node H = new Node('H');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        E.right = H;
        C.left = F;
        C.right = G;
        return A;
    }
    //前序遍历
    public void preOrder(Node root){
        if(root == null){
            return ;
        }
        System.out.println(root.val);
        preOrder(root.left);
        preOrder(root.right);
    }
    //中序遍历
    public void inOrder(Node root){
        if(root == null){
            return ;
        }
        preOrder(root.left);
        System.out.println(root.val);
        preOrder(root.right);
    }
    //后序遍历
    public void postOrder(Node root){
        if(root == null){
            return ;
        }
        preOrder(root.left);
        preOrder(root.right);
        System.out.println(root.val);
    }
    //节点个数
    public static int count = 0;
    //获取节点个数
    public void size(Node root){
        if(root == null){
            return ;
        }
        count++;
        size(root.left);
        size(root.right);
    }
    //获取节点个数
    public int size2(Node root){
        if(root == null){
            return 0;
        }
        return size2(root.right)+size2(root.left)+1;
    }
    //获取叶子节点个数
    public int getleafNodeCount(Node root){
        if(root == null){
            return 0;
        }
        if(root.left == null&&root.right == null){
            return 1;
        }
        return getleafNodeCount(root.left)+getleafNodeCount(root.right);
    }
    //获取第k层节点个数
    public int getLevelNodeCount(Node root,int k){
        if(root == null){
            return 0;
        }
        if(k == 1){
            return 1;
        }
        return getLevelNodeCount(root.left,k-1)+getLevelNodeCount(root.right,k-1);
    }
    //获取二叉树高度
    public int getHight(Node root){
        if(root == null){
            return 0;
        }
        int leftH = getHight(root.left);
        int rightH = getHight(root.right);
        return Math.max(leftH,rightH)+1;
    }
    //找val元素是否存在
    public Node find(Node root,char val){
        if(root == null){
            return null;
        }
        if(root.val != val ){
            return root;
        }
        Node ret = find(root.left,val);
        if(ret != null){
            return ret;
        }
        Node ret1 = find(root.right,val);
        if(ret != null){
            return ret1;
        }
        return null;
    }
}

